package _dp

import org.junit.Assert
import org.junit.Test

/**
 * https://leetcode.cn/problems/house-robber-ii/description/
 * https://blog.csdn.net/2303_79786049/article/details/141503133
 *
 * ```
 * 213. 打家劫舍 II
 * 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
 *
 * 示例 1：
 * 输入：nums = [2,3,2]
 * 输出：3
 * 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
 *
 * 示例 2：
 * 输入：nums = [1,2,3,1]
 * 输出：4
 * 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
 *      偷窃到的最高金额 = 1 + 3 = 4 。
 * 示例 3：
 * 输入：nums = [1,2,3]
 * 输出：3
 *
 *
 * 提示：
 * 1 <= nums.length <= 100
 * 0 <= nums[i] <= 1000
 * ```
 *
 */
class leetcode_213 {
    @Test
    fun test_1() {
        val actual = rob(intArrayOf(2, 3, 2))
        val expected = 3
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_2() {
        val actual = rob(intArrayOf(1, 2, 3, 1))
        val expected = 4
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_3() {
        val actual = rob(intArrayOf(1, 2, 3))
        val expected = 3
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_51() {
        val actual = rob(intArrayOf(200, 3, 140, 20, 10))
        val expected = 340
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_51_2() {
        val actual = rob(intArrayOf(200, 3, 140, 20, 10))
        val expected = 340
        Assert.assertEquals(expected, actual)
    }

//    fun rob(nums: IntArray): Int {
//        if (nums.size == 1) {
//            return nums[0]
//        }
//
//        // 因为是环，头和尾只能选择1个， 所以把环转换成非环
//        // 考虑头: [0, n-2]
//        val max1 = rob(nums, 0, nums.size - 2)
//        // 考虑尾: [1,n-1]
//        val max2 = rob(nums, 1, nums.size - 1)
//        return Math.max(max1, max2)
//    }
//
//    fun rob(nums: IntArray, start: Int, end: Int): Int {
//        // 1 确定递推公式：dp[i] = max(dp[i-1], num[i] + dp[i-2])
//
//        if (start == end) {
//            return nums[start]
//        }
//
//        // 2 确定dp 以及初始化
//        // 第2天，打劫和不打劫的最大值
//        val dp: IntArray = IntArray(nums.size)
//        dp[start] = nums[start]
//        dp[start + 1] = Math.max(dp[start], nums[start + 1])
//
//        // 3 确定遍历顺序
//        for (i in start + 2..end) {
//            dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2])
//        }
//        return dp[end]
//    }

    fun rob(nums: IntArray): Int {
        /**
         * 题型：动态规划
         *
         * 思路：
         * 因为是环，头和尾只能选择1个， 所以把环转换成非环
         * 取两种情况，考虑头/考虑尾，的最大值
         */
        if (nums.size == 1) {
            return nums[0]
        }
        // 考虑头：[0,size-1)
        val nums1 = nums.sliceArray(0 until nums.size - 1)
//        println(nums1.contentToString())
        val v1 = collect(nums1)

        // 考虑尾：[1,size)
        val nums2 = nums.sliceArray(1 until nums.size)
//        println(nums2.contentToString())
        val v2 = collect(nums2)

        // 取两种情况的最大值
        return Math.max(v1, v2)
    }

    fun collect(nums: IntArray): Int {
        if (nums.size == 1) {
            return nums[0]
        }
        //  println(nums.contentToString())
        // 1 确定数组以及下标
        // 第i天偷与不偷的最大值
        val dp: IntArray = IntArray(nums.size)
        // 2 确定递推公式
        // 3 初始化数组
        dp[0] = nums[0]
        dp[1] = Math.max(nums[1], dp[0])
        // 4 遍历数组
        for (i in 2 until nums.size) {
            // TODO:偷
            val v1 = nums[i] + dp[i - 2]
            // TODO:不偷
            val v2 = dp[i - 1]
            dp[i] = Math.max(v1, v2)
        }
        // 5 打印数组
        // println(dp.contentToString())
        return dp.last()
    }
}